package com.camus.datastructureandalgorithm.algorithm.sort;

import java.util.Random;

/**
 * @author jie.deng 快速排序
 */
public class QuickSortArray2 implements SortArray {

    @Override
    public int[] sortArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return nums;
        }

        // 原地排序
        sortArray(nums, 0, nums.length - 1);

        return nums;
    }

    private void sortArray(int[] nums, int lIdx, int rIdx) {
        // 递推公式: quick_sort(p...r) = quick_sort(p...q-1) + quick_sort(q+1...r)
        // 终止条件: p>=r
        if (lIdx >= rIdx) {
            return;
        }

        // 获取分区点
        int q = partition(nums, lIdx, rIdx);
        sortArray(nums, lIdx, q - 1);
        sortArray(nums, q + 1, rIdx);
    }

    private int partition(int[] nums, int lIdx, int rIdx) {
        // 选择基准
        int pivotIdx = choosePivot(nums, lIdx, rIdx);
        int pivot = nums[pivotIdx];
        if (pivotIdx != rIdx) {
            // 交换基准与最后一个元素
            nums[pivotIdx] = nums[rIdx] ^ nums[pivotIdx];
            nums[rIdx] = nums[rIdx] ^ nums[pivotIdx];
            nums[pivotIdx] = nums[rIdx] ^ nums[pivotIdx];
        }

        // 索引pivotIdx前面的元素都小于pivot
        pivotIdx = lIdx;
        
        for (int j = lIdx; j < rIdx; j++) {
			if (nums[j]<pivot) {
				if (pivotIdx != j) {
					nums[pivotIdx] = nums[j] ^ nums[pivotIdx];
					nums[j] = nums[j] ^ nums[pivotIdx];
					nums[pivotIdx] = nums[j] ^ nums[pivotIdx];
				}
	            pivotIdx++;
			}
		}
        
        // 交换基准与最后一个元素
        if (pivotIdx != rIdx) {
	        nums[pivotIdx] = nums[rIdx] ^ nums[pivotIdx];
	        nums[rIdx] = nums[rIdx] ^ nums[pivotIdx];
	        nums[pivotIdx] = nums[rIdx] ^ nums[pivotIdx];
        }
        return pivotIdx;
    }

    private int choosePivot(int[] nums, int lIdx, int rIdx) {
        return new Random().nextInt(rIdx - lIdx) + lIdx;
    }

}
